#include "permuteUnique.h"
void backtrack(std::vector<int> &nums, std::vector<std::vector<int>> &res,
               int idx, std::vector<int> &perm, std::vector<bool> &vis) {
    if (idx == nums.size()) {
        res.emplace_back(perm);
        return;
    }
    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
        if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
            continue;
        }
        perm.emplace_back(nums[i]);
        vis[i] = true;
        backtrack(nums, res, idx + 1, perm, vis);
        vis[i] = false;
        perm.pop_back();
    }
}

std::vector<std::vector<int>> permuteUnique(std::vector<int> &nums) {
    std::vector<std::vector<int>> res;
    std::vector<int> perm;
    std::vector<bool> visited;
    visited.resize(nums.size());
    std::sort(nums.begin(), nums.end());
    backtrack(nums, res, 0, perm, visited);
    return res;
}
